1. Field of the Invention
This invention is related to the field of processors and, more particularly, to tracking dependencies for instructions and scheduling instructions for execution in a processor.
2. Description of the Related Art
Processors frequently implement out-of-order execution to improve instruction execution performance. In order to obtain additional performance benefits, it is desirable to have a large “scheduling window.” The scheduling window is the window of instructions in the instruction stream being executed from which the processor can schedule instructions for execution. Typically, the size of the scheduling window is determined by the amount of buffering implemented by the processor for fetched instructions awaiting execution in the processor. Instructions which are not dependent on one another can execute in any order as a general rule, although some instruction sets do implement ordering rules with respect to some instructions (e.g. memory reference instructions such as loads and stores, synchronizing instructions, etc.). Accordingly, the larger the scheduling window, the more likely the processor will find instructions which can be executed at any given point in time. However, the larger the scheduling window, the longer the scheduling process takes.
A scheduling mechanism typically includes tracking dependencies between instructions, determining instructions that are available to execute (i.e. the instructions which have their dependencies satisfied), and scheduling instructions for execution from the instructions that are available to execute. Once instructions are scheduled, based on the execution latency of the scheduled instructions, dependent instructions on the scheduled instructions become available to schedule. Generally, a instruction is dependent on another instruction if that instruction uses the result of the other instruction as a source operand. In some cases, an instruction may be dependent on another instruction if the other instruction is required to execute first, even if the instruction does not use the result of the other instruction as a source operand.
For short execution latency instructions (e.g. many integer instructions, in most processor instruction set architectures (ISAs)), the delay from scheduling a given instruction to determining that its dependent instructions are eligible for scheduling and scheduling those instructions is critical to performance. That is, the result of the short execution latency instruction is available quickly, and thus the delay in scheduling dependent instructions may unnecessarily delay the execution of the dependent instructions. In the case that no other instructions in the scheduling window are schedulable during the delay, performance is lost.